#include <stdlib.h>
#include <stdio.h>

typedef char DataType;
typedef struct Node
{
    DataType data; /*数据域*/
    struct Node *leftChild;/*左子树指针*/
    struct Node *rightChild;/*右子树指针*/
} BiTreeNode;/*结点的结构体定义*/

// root_p 指向已经被正确初始化的 BiTreeNode
// pre_order_seq 是前序遍历时得到的字符串序列，其中每个空左子节点或者空右子节点均用 # 表示
// current_index_p 是指针，所指向的值用于记录在 pre_order_seq 中等待被处理的字符的位置；第一次调用 _recur_create_tree 函数时，其值为0
// num_elements 指出 pre_order_seq 里包含的字符个数
void _recur_create_tree(BiTreeNode * root_p, char * pre_order_seq, int * current_index_p, int num_elements) {
    // 如果current_index_p指向的值已经等于或者超过num_elements，那么程序返回（否则就会超出 pre_order_seq 提供的字符范围）
    if (*current_index_p >= num_elements){
        exit(-1);
    }
    // 把在 *current_index_p 位置上的字符 设置为 root_p 所指向的结点的数据
    root_p -> data = pre_order_seq[*current_index_p];

    // 更新 *current_index_p 使其指向下一个待扫描的字符
    *current_index_p = *current_index_p + 1;

    // 判断是否要建立左子树
    // 如果 下一个带扫描的字符 为 #：
    //   那么不用新建左子节点（为什么？）而是让左子节点为NULL，并继续相应地更新 *current_index_p 使其指向下一个扫描的字符(从而消耗掉#字符)
    // 否则
    //   新建左子节点，并递归调用 本函数 _recur_create_tree
    if (pre_order_seq[*current_index_p] == '#') {
        root_p->leftChild = NULL;
        *current_index_p = *current_index_p + 1;
    }else{
        root_p->leftChild=(BiTreeNode *)malloc(sizeof(BiTreeNode));
        _recur_create_tree(root_p->leftChild, pre_order_seq, current_index_p,num_elements);

    }

    // 判断是否要建立右子树
    // 如果 下一个带扫描的字符 为 #：
    //   那么不用新建右子节点（为什么？）而是让右子节点为NULL，并继续相应地更新 *current_index_p 使其指向下一个扫描的字符(从而消耗掉#字符)
    // 否则
    //   新建右子节点，并递归调用 本函数 _recur_create_tree
    if(pre_order_seq[*current_index_p]=='#'){
        root_p->rightChild = NULL;
        *current_index_p = *current_index_p + 1;
    } else{
        root_p->rightChild=(BiTreeNode *)malloc(sizeof (BiTreeNode));
        _recur_create_tree(root_p->rightChild,pre_order_seq,current_index_p,num_elements);
    }
}

// 根据带有显式空子节点的先序序列，构建二叉树，将其头节点的指针存入root_pp中
// 初始传入的root_pp的值无任何意义（也即root_pp尚未被正确地初始化，也即是需要你来初始化）
// pre_order_seq 指向的字符串类似 "ABC##DE#G##F###"，其中 # 表示显式的空子节点，这一类空子节点并不需要被创建对应的struct Node或者BiTreeNode
void create_tree(BiTreeNode ** root_pp, char * pre_order_seq, int num_elements) {
    // 初始化整棵树的根节点
    if (!(* root_pp = (BiTreeNode *)malloc(sizeof(BiTreeNode))))
        exit(-1);
   // (* root_pp)->leftChild = NULL;
   // (* root_pp)->rightChild = NULL;
   BiTreeNode * root_p = *root_pp;

    // 使用合适的参数调用上面定义的 _recur_create_tree 函数
    int current_index = 0;//定义参数
    _recur_create_tree(root_p,pre_order_seq,&current_index,num_elements);
}


// 递归地销毁由*root指向根节点的树：释放该树所被动态分配的内存空间
void Destroy(BiTreeNode **root)
{
    if ((*root) !=NULL && (*root)->leftChild != NULL) //不满足
        Destroy(&(*root)->leftChild);
    if ((*root) !=NULL && (*root)->rightChild != NULL)
        Destroy(&(*root)->rightChild);

    free(*root);
}

//使用visit(item)函数前序遍历二叉树t
void PreOrder(BiTreeNode *t, void visit(DataType item))
{
    if(t!=NULL){ //根-左-右
        visit(t->data);
        PreOrder(t->leftChild,visit);
        PreOrder(t->rightChild,visit);
    }
}

//使用visit(item)函数中序遍历二叉树t
void InOrder(BiTreeNode *t, void visit(DataType item))
{
    if (t!=NULL){//左-根-右
        InOrder(t->leftChild,visit);
        visit(t->data);
        InOrder(t->rightChild,visit);
    }
}

//使用void visit(DateType item)函数后序遍历二叉树t
void PostOrder(BiTreeNode *t, void visit(DataType item)) {
    if (t != NULL) {//左-右-根
        PostOrder(t->leftChild, visit);
        InOrder(t->rightChild, visit);
        visit(t->data);

    }
}
void Visit(DataType item) {
    printf("%c ", item);
}

// 查找元素值x是否在二叉树中
// 如果找到，返回值为x的结点的指针，否则返回NULL
BiTreeNode *Search(BiTreeNode *root, DataType x) {   //先序方式递归查找元素，x是否在二叉树中
    BiTreeNode *find = NULL;
    if (root != NULL) {
        if (root->data == x) {
            find = root;
        } else {
            find = Search(root->leftChild, x);
            if (find == NULL) {
                find = Search(root->rightChild, x);
            }
        }
    }
    return find;
}


    void main(void) {
        BiTreeNode *root, *p, *pp, *find;

        char *pre_order_seq = "ABC##DE#G##F###";
        create_tree(&root, pre_order_seq, 15);

        PreOrder(root, Visit); // 输出应该为 A B C D E G F
        printf("\n");
        InOrder(root, Visit); // 输出应该为 C B E G D F A
        printf("\n");
        PostOrder(root, Visit); // 输出应该为 C G E F D B A

        char x = 'E';
        find = Search(root, x);
        if (find != NULL)
            printf("\n数据元素%c在二叉树中 \n", x);
        else
            printf("\n数据元素%c不在二叉树中 \n", x);

        x = 'H';
        find = Search(root, x);
        if (find != NULL)
            printf("\n数据元素%c在二叉树中 \n", x);
        else
            printf("\n数据元素%c不在二叉树中 \n", x);

        Destroy(&root);
    }
